package 字符串.middle;

import java.util.ArrayList;
import java.util.List;

/**
 * LWZ TODO : 2020/8/27
 * 很难想到使用深度优先搜索
 */

/**
 * @author Lw中
 * @date 2020/8/27 11:08
 */
public class ErEr {
    int n;
    ArrayList<String> list = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        this.n = n;
        int left = 0;
        int right = 0;
        dfs(0, 0, "");
        return list;
    }
    /**
     * 使用深度优先搜索算法，递归查找符合条件的字符串
     * @param left
     * @param right
     * @param str
     */
    public void dfs(int left, int right, String str) {
        if (right == left && n == left) {
            list.add(str);
        }
        if (left+1<=n) {
            dfs(left+1, right, str+"(");
        }
        if (right+1<=left) {
            dfs(left, right+1, str+")");
        }
    }
}
